/**
 * Exercise 9.63
 * -----------------------------------------------------------------------------
 * Implement `insert` for binomial queues by just using the `join` operation explicitly.
 * -----------------------------------------------------------------------------
 */
#include <assert.h>
#include <stdlib.h>

typedef char Item;
typedef struct PQnode* PQlink;
typedef struct pq* PQ;

struct PQnode {
    Item key;
    PQlink l;
    PQlink r;
};

struct pq {
    PQlink *bq;
};

#define maxBQsize 4
#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)

static PQlink z = NULL;

/////////////////////////////////接口操作////////////////////////////////////
PQ PQinit();
PQlink PQinsert(PQ pq, Item v);
void PQjoin(PQ a, PQ b);

///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q);
void BQjoin(PQlink *a, PQlink *b);

//////////////////////////////////测试用例/////////////////////////////////
void test_insert();

int main(int argc, char *argv[]) {
    test_insert();
    return 0;
}


PQlink pair(PQlink p, PQlink q) {
    if (p->key < q->key) {
        p->r = q->l;
        q->l = p;
        return q;
    }else {
        q->r = p->l;
        p->l = q;
        return p;
    }
}

void BQjoin(PQlink *a, PQlink *b) {
    int i;
    PQlink c = z;
    for (i = 0; i < maxBQsize; i++) {
        switch (test(c != z, b[i] != z, a[i] != z)) {
            case 2:
                a[i] = b[i];
                break;
            case 3:
                c = pair(a[i], b[i]);
                a[i] = z;
                break;
            case 4:
                a[i] = c;
                c = z;
                break;
            case 5:
                c = pair(c, a[i]);
                a[i] = z;
                break;
            case 6:
            case 7:
                c = pair(c, b[i]);
                break;
            default:
                break;
        }
    }
}



PQ PQinit() {
    PQ pq = (PQ)malloc(sizeof(*pq));
    pq->bq = (PQlink *)malloc(maxBQsize * sizeof(PQlink));

    int i;
    for (i = 0; i < maxBQsize; i++) {
        pq->bq[i] = z;
    }

    return pq;
}

PQlink PQinsert(PQ pq, Item v) {
    PQlink t = malloc(sizeof(*t));
    t->key = v;
    t->l = z;
    t->r = z;

    PQ tempPQ = PQinit();
    tempPQ->bq[0] = t;

    PQjoin(pq, tempPQ);
    return t;
}

void PQjoin(PQ a, PQ b) {
    BQjoin(a->bq, b->bq);
}

void test_insert() {
    PQ pq = PQinit();
    // E-A-S-Y-Q-U-E-S-T-I-O-N
    PQinsert(pq, 'E');
    PQinsert(pq, 'A');
    PQinsert(pq, 'S');
    PQinsert(pq, 'Y');
    PQinsert(pq, 'Q');
    PQinsert(pq, 'U');
    PQinsert(pq, 'E');
    PQinsert(pq, 'S');
    PQinsert(pq, 'T');
    PQinsert(pq, 'I');
    PQinsert(pq, 'O');
    PQinsert(pq, 'N');

    assert(pq->bq[0] == z);
    assert(pq->bq[1] == z);
    assert(pq->bq[2]->key == 'T');
    assert(pq->bq[2]->r == z);
    assert(pq->bq[2]->l->key == 'O');
    assert(pq->bq[2]->l->l->key == 'N');
    assert(pq->bq[2]->l->r->key == 'I');
    assert(pq->bq[3]->key == 'Y');
    assert(pq->bq[3]->r == z);
    assert(pq->bq[3]->l->key == 'U');
    assert(pq->bq[3]->l->l->key == 'S');
    assert(pq->bq[3]->l->r->key == 'E');
    assert(pq->bq[3]->l->l->l->key == 'E');
    assert(pq->bq[3]->l->l->r->key == 'Q');
    assert(pq->bq[3]->l->r->l->key == 'A');
    assert(pq->bq[3]->l->r->r->key == 'S');
}